In [8]:
class SingleLinkedList(object):
"""
Single linked list.
"""
# Dunder Methods...
def __init__(self):
self.head = None
def __str__(self):
return ','.join(str(x) for x in self.iterator)
def __iter__(self):
return self.iterator
# Public Instance Properties...
@property
def iterator(self):
return (x.data for x in self._iterator)
@property
def size(self):
return sum(1 for x in self.iterator)
@property
def is_empty(self):
return self.head is None
# Public Instance Methods...
def pop(self):
self.head = self.head.next_node
def append(self, data):
new_node = self._SingleLinkedListNode(data)
if self.is_empty:
self.head = new_node
else:
for node in self._iterator: pass
node.next_node = new_node
def insert(self, index, data):
index = max(0, index)
new_node = self._SingleLinkedListNode(data)
try:
it = self._iterator_with_prev
for i in range(index + 1):
prev, node = next(it)
if prev is not None:
prev.next_node = new_node
else: # insert at head
self.head = new_node
new_node.next_node = node
except StopIteration:
prev.next_node = new_node
def remove(self, data):
if not self.is_empty:
for prev, node in self._iterator_with_prev:
if node.data == data:
if prev is None: # head
self.head = self.head.next_node
else:
prev.next_node = node.next_node
break
def index_of(self, data):
for i, node in enumerate(self._iterator):
if node.data == data:
return i
return None
# Protected Instance Properties...
@property
def _iterator(self):
if not self.is_empty:
for item in (x[1] for x in self._iterator_with_prev):
yield item
@property
def _iterator_with_prev(self):
it = self.head
prev = None
while True:
yield prev, it
if it.next_node == None:
break
prev = it
it = it.next_node
# Protected Sub Classes...
class _SingleLinkedListNode:
def __init__(self, data):
self.next_node = None
self.data = data
def __str__(self):
return str(self.data)
l = SingleLinkedList()
# append
l.append(10)
l.append(11)
l.append(12)
l.append(13)
print l
# remove
SingleLinkedList().remove(12)
l.remove(13)
l.remove(10)
print l
# append after remove
l.append(13)
print l
# insert
l.insert(0, 13)
l.insert(0, 13)
l.insert(0, 13)
l.insert(0, 13)
l.insert(0, 13)
l.insert(6, 100)
l.insert(999, 100)
l.insert(-1, 100)
print l
# is_empty
print SingleLinkedList().is_empty
print l.is_empty
# size
print l.size
# index_of
i = l.index_of(12)
l.insert(i, 999)
print l
# pop
for i in range(l.size):
l.pop()
print l
# remove until empty
l.append(0)
print l
l.remove(0)
print l.head